package wh.链表逆置;

import java.util.List;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/11/24 15:42
 * @description:链表逆置
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(null,new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4)))));
        reverseList(listNode);
        System.out.println(listNode.next.val);
    }

    public static ListNode sortList(ListNode listNode){
        //头指针
        ListNode head = listNode;
        //指向首节点
        ListNode p = listNode.next;
        head.next = null;
        while (p.next != null){
            //哨兵
            ListNode q = p.next;
            //采用头插法进行插入
            p.next = head.next;
            head.next = p;
            p = q;
        }
        p.next = head.next;
        head.next = p;
        return head;
    }

    public static ListNode reverseList(ListNode head){
       ListNode pre = new ListNode(0);
       pre.next = null;
       while (head != null){
           ListNode q = head.next;
           //头插法
           head.next = pre.next;
           pre.next = head;
           head = q;
       }
       return pre.next;
    }

}
